﻿/* ***************************************
 * 赤黒木RBTreeを構成するクラスファイル
 * *************************************** */
#include "addBST.h"
using namespace std;

// ノードの色を設定する
#define     BLACK   1
#define     RED     0

class rbtree : public BST {
    public:
        int		Rearrange;
        int		Reduce;
        int		Pushup;

    public:
        rbtree() {
            // 初期値の設定
            BST::BST();     // BSTクラスのコンストラクタを呼び出す
            this->NIL->color = BLACK;

            Rearrange = 0;
            Reduce = 0;
            Pushup = 0;
        }

        int insert( int key ) {
            node*   p;
            node*	x;
            p = BST::insert( key );         //bst手順で
            if( p==NULL ) {
                return 0;                   // すでに挿入したいデータが挿入されているなら、そのまま終了。
            }
            p->color = RED;                 //赤点として挿入

            if( p == root ) {
                p->color = BLACK;
                return 1;
            }
            x = p;

            while( p != root && p->parent->color == RED ) {
                if( uncle(p)->color == RED ) {   //Pushup
                    p = InsPushup( p );
                } else {       //Rearrange
                    InsRearrange(p);
                    break;
                }
            }
            root->color = BLACK;  //根を黒に
            return 1;
        }

        int remove( int key ) {
            node * y_point, *x_point;
            y_point = BST::remove( key );
            if( y_point == NULL ) {
                return 0;
            }
            // xをyの子とする。
            if( y_point->left != NIL ) {
                x_point = y_point->left;
            } else {
                x_point = y_point->right;
            }
            //以降、木の修正
            if( y_point->color == BLACK){  //yが黒
                while( x_point->color == BLACK && x_point!=root){  //xが黒
                    if( sibling(x_point)->color == RED){ //xの兄弟が赤ならReduce
                        DelReduce(x_point);
                    }
                    //この時点で、xの兄弟は必ず黒
                    if(sibling(x_point)->left->color == BLACK && sibling(x_point)->right->color == BLACK){
                        x_point = DelPushup(x_point); //甥が2つとも黒ならPushup
                    } else {
                        DelRearrange(x_point);   //甥の片方は赤なのでRearrange
                        break;
                    }
                }
                x_point->color = BLACK;
            } else {
            }
            return 0;
        }

        
    private:
        /*
         * 挿入操作時のPushupを指定された点で行う。
         */
        node* InsPushup( node *x_point ) {
            x_point->parent->color = BLACK;
            uncle(x_point)->color = BLACK;
            x_point->parent->parent->color = RED;

            return x_point->parent->parent;
        }

        /*
         * 削除操作時のPushupを指定された点で行う
         */
        node* DelPushup( node *x_point ) {
            sibling(x_point)->color = RED;
            x_point = x_point->parent;
            Pushup++;
            return x_point;
        }

        void DelReduce( node* x ) {
            if( x == x->parent->left ) {
                rotation( x->parent, LEFT );
            } else if( x == x->parent->right ) {
                rotation( x->parent, RIGHT );
            } else {
                cerr << "RBTree::DelReduce: #03\n";
                exit(1);
            }
            x->parent->color = RED;
            x->parent->parent->color = BLACK;
            Reduce ++;
        }

        /*
         * 挿入Rearrangeケース
         * siblingに変形後、再配色
         */
        node* InsRearrange(node* point){
            node* x = ToSiblingPath(point);
            if(x!=NULL){
                x->color=BLACK;
                x->left->color = RED;
                x->right->color = RED;
            }
            return NULL;
        }

        /*
         * 削除Rearrangeケース ( 4/19 修正 )
         * pointに甥が存在し、その子どちらか片方は赤を前提とする。
         * 甥、その親、祖父のパスをsiblingに変形後、再配色。
         */
        void DelRearrange(node* point){
            node* x = NULL;

            if( sibling(point)->left->color == RED)
                x = ToSiblingPath( sibling(point)->left);
            else
                x = ToSiblingPath( sibling(point)->right);

            //sibling真ん中点は、元その位置の点の色のまま。
            x->color = point->parent->color;
            //その子は2つとも黒に。
            x->left->color = BLACK;
            x->right->color = BLACK;
            Rearrange++;
        }
};

